package algorithm.poj.p2000;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 对比poj1753，分析方法一致。
 * 
 * 实现方式：
 * 操作码：
 * 1111_1000_1000_1000	0xF888
 * 1111_0100_0100_0100	0xF444
 * 1111_0010_0010_0010	0xF222
 * 1111_0001_0001_0001	0xF111
 * ......
 *
 * 状态"-"对应1，"+"对应0。
 * 用一个s[65536]保存状态I到目标状态(0x1111_1111_1111_1111)的最少步骤。
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P2965 {

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));

        String input = ""; 
		if (false) {
	        String line;
	        
	        for (int i = 0; i < 4; i ++) {
	        	line = stdin.readLine();
	        	input += line.trim();
	        }
	        input = input.trim().replaceAll("\\-", "1").replaceAll("\\+", "0");
		} else {
			input = "1011111111111011";
		}
        
        String output = "";
        String r = flip(input);
        if (r == null) {
        	output += "Impossible";
        } else {
            output += r; 
        }
        
        System.out.println(output);
	}
	
	private static Integer[] initialize() {
		
		//初始化状态数组
		Integer[] s = new Integer[65536];
		for (int i = 0; i < s.length; i ++) s[i] = null;
		
		//初始化queue状态
		Queue q = new Queue(65536);
		q.put((int)0xFFFF);
		s[(int)0xFFFF] = 0;

		int ops[] = {
				0xF888, 0xF444, 0xF222, 0xF111,
				0x8F88, 0x4F44, 0x2F22, 0x1F11,
				0x88F8, 0x44F4, 0x22F2, 0x11F1,
				0x888F, 0x444F, 0x222F, 0x111F
		};
		
		//start
		//s[i] 保存的信息包括上一个节点n,以及当前的步骤i。
		//如果s[i]保存达到状态i的结果字符串，运行效率很差。（是当前版本4+倍时间）
		//
		while (!q.isEmpty()) { 
			int n = q.get();
			for (int i = 0; i < ops.length; i ++) {
				int m = (int)(n^ops[i]);
				if (s[m] == null) {
					s[m] = (n<<4) + i;
					q.put(m);
				}
			}
		}

		return s;
	}

	private static String flip(String input) {

		int n = Integer.valueOf(input, 2);
		Integer[] s = initialize();

		String r = "";
		int c = 0;
		int m = n;
		while (m != 0xFFFF) {
			int i = s[m]%16;
			r = ((i>>2)+1) + " " + (i%4+1) + "\r\n" + r;
			c ++;
			m = s[m]>>4;
		}
		
		return c + "\r\n" + r;
	}
	

	private static class Queue {
		
		//用数组模拟一个Queue
		int q[];
		int start;
		int end;
		
		public Queue(int volumn) {
			
			this.q = new int[volumn];
			for (int i = 0; i < this.q.length; i ++) this.q[i] = -1;
			this.start = 0;
			this.end = 0;
		}
		
		public void put(int n) {
			
			int size = this.end-this.start;
			if (size < 0) {
				size += this.q.length;
			}
			if (size == this.q.length) {
				throw new RuntimeException("Queue is Full!");
			} else {
				this.q[this.end] = n;
				if (this.end == this.q.length-1) {
					this.end = 0;
				} else {
					this.end = this.end+1;
				}
			}
		}
		
		public int get() { 
			
			if (this.end == this.start) {
				throw new RuntimeException("Queue is Empty!");
			} else {
				int n = this.q[this.start];
				if (this.start == this.q.length-1) {
					this.start = 0;
				} else {
					this.start = this.start+1;
				}
				return n;
			}
		}
		
		public boolean isEmpty() {
			return this.end == this.start;
		}
	}

}
